/*
 * LocalGraphPartitioning.java
 *
 * This file is part of FUJIWARA.
 * Copyright (C) 2010 Loris Fichera    (loris.fichera@gmail.com)
 *                    Daniele Marletta (danielemar86@gmail.com)
 *
 * FUJIWARA is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * FUJIWARA is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with FUJIWARA.  If not, see <http://www.gnu.org/licenses/>.
 */

package graphclient;

import java.util.ArrayList;

/**
 *
 * @author Loris Fichera
 * @author Daniele Marletta
 *
 */
public class LocalGraphPartitioning extends GraphPartitioningStrategy {

    //private static final String IC = "IC";

    public int [] countNeighbours (int [][] adjMatrix) {
        int [] neighbourCount= {};
        return neighbourCount;
    }

    public String [] processConnections (int [] neighbourCount) {
        String [] connectionVectors = {};
        return connectionVectors;
    }


    /**
     * Compute, for every node of the net, the number of hops from
     * an hyperconnected node.
     * NOTE: in the following, the term 'hypernode' is used as a synonim
     * of hyperconnected node.
     *
     * @param adjVector is the adjacency matrix vectorialized.
     * @param neighbourCount is an array that, for every index, contains
     * the total number of neighbours of the corresponding node.
     * @param hyperNodeIndex is the index of the neighbourCount where the
     * hypernode is located.
     * @return  the propagation vector which, for every index, contains the number
     * of hops of the node from the hyperNode.
     */
    public int [] computeHops ( int [] adjVector,
                                     int [] neighbourCount,
                                     int hyperNodeIndex) {


        Double dSize = new Double(adjVector.length);
        dSize = Math.sqrt(dSize);
        /** Total number of nodes in the network. */
        final int SIZE = dSize.intValue();

        /** Rebuild the adjacency Matrix. */
        int [][] adjMatrix = new int[SIZE][SIZE];
        int k = 0;
        for (int i = 0; i < SIZE; i ++) {
            for ( int j = 0; j < SIZE; j ++) {
                adjMatrix[i][j] = adjVector[k];
                k++;
            }
        }

        /** Build the array of Node objects. */
        Node [] nodes = new Node [SIZE];

        int clusterID = 0;
        for (int index = 0; index < SIZE; index++)  {
            if ( index == hyperNodeIndex)
            {
                // Add the hyperconnected node on top of the list
                nodes[index] = new HyperNode(neighbourCount[index], new Integer(++clusterID).toString());
                

            } else {
                nodes[index] = new Node(neighbourCount[index]);
            }
        }
          
        /**
         * Rebuild the topology of the node by using Node objects.
         */
        Node currentNode;
        for (int row=0; row<SIZE; row++){
            currentNode = nodes[row];
            for(int column=0; column<SIZE; column++){
                if (adjMatrix[row][column] == 1){
                    currentNode.addNeighbour(nodes[column]);
                }
            }
        }


        Node hyperNode = nodes[hyperNodeIndex];
        /** Execute the algorithm. */
        hyperNode.propagate();

        int [] propagationArray = new int [SIZE];

        for (int i=0; i<SIZE; i++){
            propagationArray[i] = nodes[i].getHops();
        }

        /** Debug Prints . */
        //System.out.println("\nTotal number of nodes : " + SIZE);
        //System.out.println("The propagation vector for Hypernode: " + hyperNode.getClusterName() + " is:");

        for (int i=0; i<SIZE; i++)  {
            System.out.print(propagationArray[i] + " ");
        }

        System.out.println();
       
        return propagationArray;
    }
}

/**
 *
 *  The generic Node of the network. Every Node holds
 *  a reference to its neighbours and keeps track of
 *  the number of hops from a particular node.
 */
class Node {

    protected int totalNeighbours;
    protected int neighboursCounter;
    protected int hops;
    protected Node [] neighbours;
    protected String clusterName;


    public Node(int neighbourCount) {
        this(neighbourCount,null,-1);
    }

    public Node(int neighbourCount, String clusterName) {
        this(neighbourCount,clusterName,-1);
    }

    public Node(int neighbourCount, String clusterName, int hops) {

        this.totalNeighbours = neighbourCount;
        neighbours = new Node [totalNeighbours];
        neighboursCounter = 0;
        
        this.clusterName = clusterName;
        this.hops = hops;
    }


    public void addNeighbour(Node neighbour){
        try {
            if (neighboursCounter < totalNeighbours ) {
                neighbours[neighboursCounter] = neighbour;
                neighboursCounter++;
            } else {
                throw new InconsistentNeighboursException();
            }
        } catch (InconsistentNeighboursException e) {
            System.out.println("Error! " + e.getMessage());

        }
    }


    /** This method should be meaningfully implemented by subclasses. */
    public void propagate() {}


    /** Getters, setters and utility methods.   */

    public boolean isReachable() {
        return (hops >= 0);
    }

    public int getHops() {
        return hops;
    }

    public void setHops(int hops) {
        this.hops = hops;
    }

    public String getClusterName() {
        return clusterName;
    }

    public void setClusterName(String name){
        clusterName = name;
    }

    public Node[] getNeighbours() {
        return neighbours;
    }

}


/**
 * Hyperconnected Node of the network. The clustering algorithm 
 * computes the hops of all nodes from a particular HyperNode.
 *
 */
class HyperNode extends Node {

    /** By using FIFO order, every Node in this list
     *  must set the hop of all its neighbours.
     */
    private static ArrayList<Node> pendingNodes;


    public HyperNode(int neighbourCount, String clusterName) {
        super(neighbourCount,clusterName,0);

        pendingNodes = new ArrayList<Node>();

    }

    /** Implements the algorithm to compute the hops of all
     * other nodes of the network from the current hypernode.
     */
    @Override
    public void propagate() {
        /** Initialize the list. */
        pendingNodes.add(this);

        while(pendingNodes.size() > 0)
        {
            /** Pop the next node to be processed. */
            Node parentNode = pendingNodes.get(0);
            pendingNodes.remove(0);
            /** Retrieve the neighbours of the node. */
            Node[] children = parentNode.getNeighbours();
            for (int i=0; i< children.length; i++) {
                Node childNode = children[i];
                if (! childNode.isReachable() ) {
                    childNode.setHops ( parentNode.getHops() + 1);
                    pendingNodes.add(childNode);
                }
            }
        }
        
    }
}


/**
 *  This exception is raised when the number of the neighbours of a Node
 *  object is different from the number declared in the input array of
 * the classify() method.  
 */
class InconsistentNeighboursException extends Exception {

    private String message;

    InconsistentNeighboursException() {
        message = "Attempt to add a neighbour so that the number of neighbours exceeds the declared total number of neighbours";
    }

    @Override
    public String getMessage() {
        return message;
    }
}

/** NOTE: following there's old code which will be soon deleted. */


        /** Keep track of the index of the hypernodes nodes. */
        //ArrayList<Integer> hyperNodeIndexes = new ArrayList<Integer>();

        /** Identify the indexes of the hypernodes. */
        /*for ( int index = 0; index < SIZE; index++ ) {
            if ( connectionClasses[index].equals(IC) ) {
                hyperNodeIndexes.add(index);
            }
        }*/


        /*
            Integer [] strengths = new Integer[nodes.size()];
            for (int j=0; j<nodes.size(); j++)
            {
                currentNode = nodes.get(j);
                strengths[j] = new Integer(currentNode.getHops());
                //strengths[j]=str.toString();
                // Reset hops
                //if ( currentNode.getHops() > 0 ) {
                    currentNode.setHops(-1);

            }
            propagationVecs.add(strengths);
        //}
*/


        /** This logic will be moved to CLient Side
        Random r = new Random();
        String [] part = new String[nodes.size()];
        for (int i=0; i<nodes.size(); i++) {
            int min = nodes.size();

            for (int j=0; j<propagationVecs.size();j++)
            {
                if (propagationVecs.get(j)[i] == -1) {
                    propagationVecs.get(j)[i] = Integer.MAX_VALUE;
                }

                if ( propagationVecs.get(j)[i] < min ) {
                    min = propagationVecs.get(j)[i];
                }
            }

            ArrayList<Integer> clusterIndex=new ArrayList<Integer>();
            for (int j=0; j<propagationVecs.size();j++)
            {
                if ( propagationVecs.get(j)[i] == min ) {
                    clusterIndex.add(j);
                }
            }

            if (clusterIndex.size()==1) {
                part[i] = nodes.get(hyperNodeIndexes.get(clusterIndex.get(0))).getClusterName();

            } else {
                int randomIndex = r.nextInt(clusterIndex.size());
                randomIndex++;
                Integer rand = randomIndex;
                part[i] = rand.toString();
            }


        }*/


       /*System.out.print("The IC nodes are: ");
       for (int i=0; i<clusterID; i++)
       {
            //System.out.print(nodesList.get(hyperNodeIndexes.get(i)).getClusterName() + ", ");
            System.out.print(hyperNodeIndexes.get(i) + ", ");
       }
       */

       /*
       for (int i=0; i<neighbourCount.length; i++)
       {
          System.out.print(neighbourCount[i] + " ");
       }
       System.out.println();
       for (int i=0; i<neighbourCount.length; i++)
       {
          System.out.print(nodesList.get(i).getNumNeighbours() + " ");
       }*/

       /*System.out.println("\n Propagations:");
       for (int i=0; i<propagationVecs.size(); i++)
       {
            Integer []  prop = propagationVecs.get(i);
            for(int j=0; j<prop.length;j++) {
                System.out.print(prop[j] + " ");
            }
            System.out.println();
       }
        */